#include <iostream>
#include <iterator>
#include <fstream>
#include <algorithm>
#include <string>
#include <vector>

typedef std::vector<std::string> dict_type;

template<typename BidirectionalIterator, typename T>
class nonAssocFinder
{
public:
  nonAssocFinder(BidirectionalIterator begin,
		 BidirectionalIterator end)
    : _begin(begin), _end(end)
  { }

  bool
  operator() (const T& word)
  {
    /*    std::cout << "DICTIONARY:" << std::endl;
    std::copy(_begin, _end, std::ostream_iterator<std::string>(std::cout, "---"));
    
    std::cout << std::endl;  
    
    std::cout << "Checking \"" << word << "\": ";
    bool s = std::binary_search(_begin, _end, word);
    if (s)
      {
	std::cout << "FOUND" << std::endl;
      }
    else 
      {
	std::cout << "NOT FOUND" << std::endl;
      }

      return s;*/

    return std::binary_search(_begin, _end, word);
  }

private:
  BidirectionalIterator _begin;
  BidirectionalIterator _end;
};

int main()
{
  std::ifstream dictFile("dict.txt");
  std::ifstream wordsFile("words.txt");

  dict_type dictionary;

  std::copy(std::istream_iterator<std::string>(dictFile),
	    std::istream_iterator<std::string>(),
	    std::back_inserter(dictionary));

  std::sort(dictionary.begin(), dictionary.end());

  
  std::cout << "DICTIONARY:" << std::endl;
  std::copy(dictionary.begin(), dictionary.end(),
	    std::ostream_iterator<std::string>(std::cout, " "));
  std::cout << std::endl;

  std::cout << "CHECKING:" << std::endl;
  std::remove_copy_if(std::istream_iterator<std::string>(wordsFile),
		      std::istream_iterator<std::string>(),
		      std::ostream_iterator<std::string>(std::cout, "\n"),
		      nonAssocFinder<dict_type::iterator, dict_type::value_type>(dictionary.begin(),
										 dictionary.end()));
	    
}
